package leetcode.二叉树;
/*
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

        如果树中有不止一个众数，可以按 任意顺序 返回。
        假定 BST 满足如下定义：
        结点左子树中所含节点的值 小于等于 当前节点的值
        结点右子树中所含节点的值 大于等于 当前节点的值
        左子树和右子树都是二叉搜索树
*/

import java.util.ArrayList;
import java.util.List;

public class 二叉搜索树中的众数501 {

    int maxTimes = 0, curTimes = 0,preVar = 0;
    private List<Integer> list = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        process(root);
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    private void process(TreeNode root) {
        if (root == null)
            return;
        process(root.left);
        if(root.val == preVar){
            curTimes++;
        }else {
            preVar = root.val;
            curTimes = 1;
        }
        if(curTimes == maxTimes)
            list.add(root.val);
        else if(curTimes > maxTimes){
            list.clear();
            list.add(root.val);
            maxTimes = curTimes;
        }
        process(root.right);
    }

}



/*  解法二:map+流式处理
class Solution {
    Map<Integer,Integer> map;
    public int[] findMode(TreeNode root) {
        map = new HashMap();
        getMode(root);
        ArrayList<Integer> list = new ArrayList<>();
        final int[] max = {0};
        map.forEach((k,v)->{
            if (v > max[0]){
                max[0] = v;
                list.clear();
                list.add(k);
            }else if (v==max[0]){
                list.add(k);
            }
        });
        return Arrays.stream(list.toArray(new Integer[0])).mapToInt(Integer::intValue).toArray();
    }
    public void getMode(TreeNode root){
        if (root==null){
            return;
        }
        Integer value = map.get(root.val);
        map.put(root.val,value==null?1:++value);
        getMode(root.left);
        getMode(root.right);
    }
}
*/
